1. Field of the Invention
The present invention relates to the field of fingerprint recognition, which is a well tried and tested technique for the identification of an individual. The present invention more specifically relates to processings to apply to digital images reproducing fingerprints to enable a comparison thereof.
2. Discussion of the Related Art
Methods and systems of fingerprint recognition based on digital images use various image-processing techniques. The aims of such processings is, generally, to improve the image definition and detect the positions of points, called minutiae, characteristic of the arrangement of the papillary lines of a fingerprint.
Among processings performed on digital images, the present invention more specifically relates to a step of determination of the orientation of the fingerprint ridges. This steps leads to the calculation of a directional image aiming at obtaining an image of the orientation of the fingerprint ridges. In other words, to each of the image pixels is assigned the orientation of the ridge to which it belongs.
Generally, this determination takes account of the image resolution and, more specifically, of the minimum and maximum widths of the ridges and valleys of the papillary arrangement in the digital image.
A first conventional method to determine the orientation of the ridges of a digital image reproducing a fingerprint consists of calculating the gradients at each point of the image in two orthogonal directions. The orientation is then determined by calculating the tangent of the gradient ratio, and this, for each image pixel. Generally, the calculations are rounded up by taking account of a limited number D of directions, for example, eight.
A second conventional method consists of calculating, for each image pixel and for an arbitrarily-chosen number D of directions, the sum of the differences between the grey level of the current pixel and the grey levels of the pixels surrounding it in each direction. On a ridge, this sum is maximum, and perpendicularly to a ridge, this sum is minimum. The minimum value obtained from the D calculated sums is thus selected, and the concerned pixel is assigned the orientation of the ridge to which it belongs. To enable such a determination, the number of pixels taken into account around the current pixel is determined according to the minimum and maximum possible widths of the ridges, and thus to the size and the resolution of the digital image.
This method amounts to applying, for each image pixel, and for each of D directions (for example, eight), the following formula:
                    K        ⁡                  (                      i            ,            j                    )                    =                          ⁢              d        ⁡                  [                                                    MIN                                  d                  =                  0                                                            D                -                1                                      ⁡                          (                                                ∑                                      k                    =                    1                                    L                                ⁢                                                                  ⁢                                                                                              C                      ⁡                                              (                                                  i                          ,                          j                                                )                                                              -                                          Cd                      ⁡                                              (                                                                              i                            k                                                    ,                                                      J                            k                                                                          )                                                                                                                          )                                ]                      ,          where      :        ⁢        
d designates the direction (d ranges between 0 and D−1, or between 1 and D);
MIN designates a function for selecting the value of d corresponding to the direction for which the sum is minimum;
K(i,j) is the orientation of the pixel of cartesian coordinates (i,j) in the resulting directional image, that is, value d assigned to the pixel;
C(i,j) is the grey level intensity of point (i,j) in the original image for which the formula is applied;
L represents the number of pixels taken into account to apply the formula, that is, the number of pixels on a line of direction d containing the point of coordinates (i,j);
k ranges between 1 and L and identifies the pixel of the line of direction d containing the point of coordinates (i,j); and
Cd(ik,jk) represents the intensity (grey level) of each pixel of rank k in the line of direction d containing the point of coordinates (i,j).
Number L (for example, equal to 13) is, in practice, determined by applying the following relation:L=2.Hd+1, where:
Hd=(Wmax−1)/2 rounded up to the next higher integer; and
Wmax represents the maximum average width of the ridge, in number of pixels in the image to be processed.
Be it by the first or the second method, a resulting or directional image is obtained in which, for each pixel, a code representing one of the D directions is provided. This code may be assimilated to a grey level since it generally corresponds to a binary word having the same size as the grey level coding (for example, an 8-bit word enabling coding from 0 to 255), and since it could be used to generate an image, the grey levels of which would differentiate the codes. Accordingly, reference will sometimes be made hereafter to “grey levels” to designate the values given to points of a matrix corresponding to image pixels, even if these values do not actually really represent grey levels of the original image.
Once the directional image has been obtained, the average orientation of blocks b dividing up this image is determined. The size chosen for the blocks is set by the number of pixels taken into account around the current pixel to determine the ridge direction, which is itself a function of the minimum and maximum possible widths (in number of pixels) of a fingerprint ridge in the considered image.
For each block b, the direction d which most frequently appears in its pixels (among the D defined directions) is determined by applying a histogram calculation to determine the most frequent direction in the concerned block. This amounts, for each block b and for each direction d, to applying the following relation:HIST(d)=Pd/X, where:
HIST represents the calculated discrete histogram function;
Pd represents the number of pixels of the directional image block having direction d, and
X represents the total number of pixels in the block.
Eight values HIST are obtained for each block and the direction d corresponding to the greatest value is chosen as the orientation O(b) of block b. This amounts to applying the following formula:
                    O        ⁡                  (          b          )                    =              d        ⁡                  [                                                    MIN                                  d                  =                  0                                                            D                -                1                                      ⁡                          (                              HIST                ⁡                                  (                  d                  )                                            )                                ]                      ,          where      :        ⁢        
MAX designates a function of selection of the value of d corresponding to the direction for which the histogram function provides the maximum value.
Different conventional processings are then implemented on the original image to more reliably determine, by means of the obtained orientation image, the respective positions of the minutiae and, on the same occasion, the orientation of the papillary arrangement which surrounds them locally.
An example of application of the above second method is described in article “Système automatique de reconnaissance d'empreintes digitales. Sécurisation de l'authentification d'une carte á puce” by Christel-Loïc Tisse, Lionel Martin, Lionel Torres, and Michel Robert, published in September 2001 in GRETSI'01 proceedings, Sept. 10-11, 2001, Toulouse (FR), which is incorporated herein by reference.
An obvious disadvantage of the first method is the large amount of complex calculations to be performed, in particular to calculate the tangents at each point in the image.
As for the second method, it requires a significant number of accesses to a memory (or memory area) in which the original image is stored.
Further, be it in the first or in the second method, a second series of memory accesses must be performed to calculate the average orientations of the blocks based on the stored directional image.
The significant number of memory accesses considerably slows down the image processing.
Moreover, the large number of pixels (several hundreds in each direction of the image) makes the execution of the calculations by groups of pixels in parallel over the entire image unrealistic. Now, in integrated applications, it is often preferable to process repetitive calculations by means of components in wired logic rather than by means of a processor executing calculation instructions of a software program.